Menurut Sejarah Melayu, Parameswara yang dilahirkan sebagai Raja Singapura terakhir yang berasal daripada keturunan Srivijaya (Hindu). Pada tahun 1324, seorang putera Srivijaya dari Bentan bernama Sang Nila Utama telah menawan Temasek dan menubuhkan kerajaan Singapura lama. Baginda memerintah selama 48 tahun dan diiktiraf sebagai Raja Singapura oleh satu utusan daripada Maharaja China pada tahun 1366. Baginda secara rasmi bergelar Sri Maharaja Sang Utama Parameswara Batara Sri Tri Buana. Batara Sri Tri Buana yang bermaksud "Yang Dipertuan kepada tiga dunia" melambangkan kekuasaan baginda ke atas Palembang, Bentan dan Temasek. Terdapat tiga orang lagi Raja daripada keturunan baginda yang memerintah Singapura iaitu, Paduka Sri Pekerma Wira Diraja (1372 – 1386), Paduka Seri Rana Wira Kerma (1386 – 1399) dan yang terakhir Paduka Sri Maharaja Parameswara (1399 – 1401). Pada 1401, kerajaan Majapahit menyerang Singapura dengan bantuan Bendahara yang belot, Sang Rajuna Tapa. Parameswara telah berjaya melarikan diri menuju ke pantai barat Semenanjung Melayu untuk membuka ibu negeri yang baru.[3][4]

Menurut "Suma Oriental", Parameswara ialah seorang raja Palembang yang menggantikan ayahandanya, Raja Sam Agi. Beliau diserang oleh Raja Jawa, Batara Tamavill, sewaktu beliau menggelarkan dirinya sebagai Mjeura ("orang yang berani"). Ekoran daripada itu, beliau melarikan diri ke Singapura. Setelah membunuh wakil Raja Siam (bernama Temagi) di Singapura, Parameswara menjadi pemerintah palsu pada satu tempoh yang tidak lama kerana beliau telah diserang dan dihalau oleh pihak Siam tidak lama selepas itu. Dengan seribu pengikutnya, beliau menuju ke pantai barat Semenanjung Melayu untuk mencari tempat perlindungan yang baru.

Menurut Sejarah Melayu yang dikarang oleh Tun Sri Lanang pada tahun 1565, angkatan Parameswara melarikan diri ke Muar tetapi diganggu oleh biawak yang tidak terkira banyaknya. Penetapan di tempat yang kedua di Kota Burok juga gagal kerana kubu pertahanan yang cuba didirikan mereka runtuh dengan serta merta. Kemudian, Parameswara berpindah ke Sening Ujong (nama lama bagi Sungai Ujong). Setelah berada di sana, beliau melantik seorang menteri untuk mewakili dirinya dan kemudiannya beliau tiba di muara Sungai Bertam (nama lama bagi Sungai Melaka). Ketika itu, orang-orang Seletar mendiami kawasan itu dan mereka meminta Parameswara menjadi Raja.[5] Parameswara merasakan kedudukan tempat itu amat baik untuk didirikan kerajaan. Tempat itu berhampiran dengan laut yang menjadi laluan kapal dagang. Bekalan air bersih juga mudah diperoleh. Selain itu, bentuk muka bumi yang berbukit-bukau boleh menjadi petunjuk kepada pelayar dan memudahkan urusan mengawal Selat Melaka. Pokok Bakau dan Api-api boleh dijadikan benteng semula jadi. Angin Monsun pula tidak mengganggu kegiatan perdagangan kerana muara sungainya terlindung daripada tiupan angin tersebut.

Semasa Parameswara sedang berehat di bawah pohon Melaka, Parameswara telah melihat peristiwa anjing pemburuannya ditendang oleh seekor pelanduk. Peristiwa ini dianggap luar biasa kerana seekor pelanduk kecil dapat mengalahkan seekor anjing. Oleh itu, Parameswara memilih untuk mendirikan sebuah kerajaan. Parameswara menamakan tempat itu Melaka bersempena dengan nama pokok beliau berteduh.

Parameswara memeluk Islam pada tahun 1409 dan telah menggelar diri baginda sebagai Raja Iskandar Syah. Baginda telah berkahwin dengan seorang puteri Pasai, Indonesia. Pada tahun 1409 juga, Laksamana Cheng Ho telah singgah di Melaka dalam rangka lawatan beliau untuk meneroka dunia.[perlu rujukan] Pada 1411, Parameswara telah membuat pelayaran melawat negara China dengan rombongan pengiring sebanyak 540 orang untuk pertemuan dengan Maharaja Ming, Yung Lo. Maharaja Yung Lo juga mengiktiraf Parameswara sebagai raja Melaka.[perlu rujukan]

Pemerintahannya itu berkembang dengan pesat dan menjadi sebuah pelabuhan yang terpenting di Kepulauan Melayu pada abad ke-15 dan ke-16. Tambahan pula, Melaka merupakan tempat perdagangan rempah dengan berfungsi sebagai pintu kepada negeri-negeri rempah untuk memasarkan rempah mereka. Keadaan ini dapat digambarkan menerusi Duarte Barbosa yang berkata :

Faktor-faktor yang menyumbang kepada Melaka menjadi sebuah negeri yang maju adalah kerana pelabuhannya terlindung daripada ancaman Monsun Barat Daya dan Monsun Timur Laut. Pedagang-pedagang dari Jawa, Arab, India, China dan lain-lain dapat berlindung di Melaka sehinggalah keadaan selamat untuk mereka ke laut semula. Semasa pemerintahan Parameswara, ramai orang Cina menetap di Melaka, berdekatan kawasan Bukit Cina yang mempunyai feng syui yang terbaik pada masa itu.